package com.cdream.basic.algorithm.leetcode.dp;

public class Question518 {
    public int change(int amount, int[] coins) {
        // 凑出金额为k的方案数
        int[] dp = new int[amount + 1];

        dp[0] = 1;
        for (int coin : coins) {
            // 选择前i个硬币，凑出1...amount的方案数量
            for (int j = 1; j <= amount; j++) {
                if (j >= coin) {
                    // 两个上一轮的方案数相加
                    dp[j] += dp[j - coin];
                }
            }
        }

        return dp[amount];
    }
}
